I. Field of the Invention
This invention relates to using VLSI architecture for high bandwidth, low latency execution of the Reed-Solomon encode, decode, and error correction functions, capable of correcting a large number of symbol errors in binary digital data.
II. Description of the Related Art
Electronic communications and data processing systems transmit, receive and store electromagnetic signals representative of binary "zeros" and "ones." During data transfer along data channels, or during the process of storing data on and retrieving data from various magnetic, optical or other storage media, erroneous data values may occur. These errors may be the result of electromagnetic noise on the data channel or defects in the storage media. Isolated single bit random errors and contiguous multibit "bursts" of errors must be recognized and corrected using a system that is highly reliable, that is, one that does not produce many errors in the corrected data. At a minimum, the erroneous data must be recognized and flagged as erroneous rather than being acted upon.
Unlike data communications systems that have the luxury of retransmitting data until an error free transmission occurs, erroneous data stored on magnetic, optical or other storage media are permanently lost unless they can be corrected. By encoding data prior to storage or transmission, and decoding following reception or retrieval, errors may be detected and corrected prior to the data being released for subsequent use. Reed-Solomon codes are effective for the types of independent and bursty errors experienced on magnetic storage media. Information on encoding, decoding, and Reed-Solomon codes in particular may be found in "Error Correcting Codes" by Peterson and Weldon, The MIT Press, second edition (1972) and several other texts.
For binary data storage and retrieval systems, error correction begins prior to storing data on the applicable medium, here considered to be a magnetic disk. First the data are encoded using an (N,K) Reed-Solomon code word of N m-bit symbols, consisting of K data symbols and N-K Error Correction Code (ECC) symbols. The ECC symbols are redundant and provide the information necessary to recognize erroneous data symbols and to reconstruct a maximum of T=(N-K)/2 data symbols.
A symbol is a series of m bits, for example, 6 or 10. The data stream of binary digits destined for storage on a disk sector usually consists of a series of 8, 16 or 32 bit words and must be converted to a series of data symbols. The N symbols of the code word are representative of the coefficients of a polynomial in x of degree N-1 represented by a(x) where deg(a)=N-1. ECC symbols are generated such that each code word is evenly divisible by a generator polynomial, g(x), having N-K consecutive roots in the Galois Field, GF (2.sup.m), and where each ECC symbol is an element .alpha..sup.i of GF(2.sup.m). The generator polynomial, g(x) is chosen based on the extent and complexity of the error correction scheme, that is, how many symbols of detection and correction are desired. In an (N,K) code, deg(g)=N-K. If d(x) is a polynomial in x of degree K-1 with K data symbols d.sub.i as coefficients, then the code word a(x) is: EQU a(x)=d(x)*x.sup.(N-K) +e(x) EQU where EQU e(x)=Remainder of [d(x)*x.sup.(N-K) /g(x)]
The coefficients of e(x) are the ECC symbols e.sub.i. This process of dividing the data symbol polynomial d(x) by the generator polynomial g(x) ensures that each stored code word a(x) is evenly divisible by g(x). If a retrieved code word y(x) is error free, y(x) is equal to a(x) and is evenly divisible by g(x). If y(x) is not evenly divisible by g(x) then that code word is assumed to contain an error vector p(x) that must be located and corrected, where y(x)=a(x)+p(x).
The factors of an error locator polynomial, NU(x), and an error evaluator polynomial, W(x), locate the erroneous data symbols within the code word and indicate the values which, when added modulo 2 to the received symbols, provide the correct symbols. The terms of NU(x) are calculated using the BerlekampMassey algorithm from the error syndromes, Si, which are obtained by dividing y(x) by the factors of g(x). If a syndrome is non-zero, then part of the code word is in error. The error location is found by computing the roots of the error locator polynomial, NU(x) and then the correct data symbol may be determined by finding the value of W(x) using the syndromes and NU(x). Root finding in a digital environment typically uses Chien's search algorithm. A Reed-Solomon encoding-decoding system that uses the technique of a generator polynomial, syndrome computation, and evaluation of error locator and error evaluator polynomials is described in U.S. Pat. No. 4,413,339 to Riggle et al.
Because of the many computations being performed in software or iteratively in hardware, and the need to calculate the NU(x) and W(x) polynomials and all the roots of NU(x), and to evaluate W(x) prior to correcting erroneous data symbols, prior art decoders suffer from one or more of the drawbacks of high latency, low bandwidth and high cost, especially when many data errors are encountered. Soft error rates for disks are therefore limited to about 1.times.10.sup.-6 because of the low processing speed or cost of the decoders. Faster Reed-Solomon systems which are also inexpensive have the drawback of being limited to correcting a maximum of only about 4 symbols per sector, which limits the tolerable soft error rates for data storage devices. Cross-interleaved Reed-Solomon decoders have a moderate bandwidth and can correct large numbers of symbol errors, but they introduce excessive storage overhead for disk systems with short disk blocks, thereby reducing the net data density permitted on the disk drive. This defeats one of the primary purposes for implementing the ECC system, which is to allow high density data storage on disk drives along with the inherently high data error rates resulting from increased density data storage.
An object of this invention is to correct higher soft bit error rates on sectorized data storage devices while providing acceptably low hard bit error rates.
Another object of this invention is to provide a high bandwidth, low latency implementation of the Reed-Solomon error correction function where a large number of symbol errors are corrected with a minimum of data storage overhead within a standard disk block.
A further object of this invention is to implement pipelining and flow control processes for executing the Berlekamp-Massey, Weng and modified Chien algorithms, and to provide novel algorithms for computing the degree of the error location polynomial and its control over the Berlekamp-Massey algorithm, so that the Reed-Solomon error correction function can be implemented in hardware in real time.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out in the appended claims.